#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>

const int N = 20, M = 1e6 + 1e5;
int ans, n, tn, cnt, suf[N + 1], a[N + 1];
bool vis[1 << N];
std::map<int, int> hash;
std::vector<int> vec[M];

void dfs(int step, int sum, int sta) {
  if (step == tn + 1) {
    if (hash.find(sum) == hash.end()) hash[sum] = ++cnt;
    vec[hash[sum]].push_back(sta);
    return;
  }
  if (std::abs(sum) > suf[step - 1]) return;
  dfs(step + 1, sum, sta);
  dfs(step + 1, sum + a[step], sta | (1 << (step - 1)));
  dfs(step + 1, sum - a[step], sta | (1 << (step - 1)));
}

void dfs2(int step, int sum, int sta) {
  if (step == tn + 1) {
    if (hash.find(sum) != hash.end()) {
      int tmp = hash[sum];
      std::vector<int>::iterator END = vec[tmp].end(), i = vec[tmp].begin();
      for (; i != END; ++i)
        if (!vis[(*i) | sta]) ++ans, vis[(*i) | sta] = true;
    }
    return;
  }
  dfs2(step + 1, sum, sta);
  dfs2(step + 1, sum + a[step], sta | (1 << (step - 1)));
  dfs2(step + 1, sum - a[step], sta | (1 << (step - 1)));
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("CppTest.in", "r", stdin);
  freopen("CppTest.out", "w", stdout);
#endif
#endif

  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = n; ~i; --i) suf[i] = suf[i + 1] + a[i];
  tn = n >> 1;
  dfs(1, 0, 0);
  tn = n;
  dfs2((n >> 1) + 1, 0, 0);
  printf("%d", ans - 1);
  return 0;
}